class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()<=1)
            return 0;
        int water=0;
        stack<int> left;
        left.push(0);
        int max_h=0;
        for(int i=0;i<height.size();i++)
        {
            if(height[i]<max_h)
            {
                left.push(height[i]);
            }
            else
            {
                while(left.size()>0)
                {
                    water+=max_h-left.top();
                    left.pop();
                }
                max_h=height[i];
                left.push(height[i]);
            }
        }
        stack<int> right;
        right.push(0);
        max_h=0;
        while(left.size()>0)
        {
            int top=left.top();
            if(top>=max_h)
            {
                while(right.size()>0)
                {
                    water+=(max_h-right.top());
                    right.pop();
                }
                max_h=top;
                
            }
            right.push(top);
            left.pop();
        }
        return water;
    }
};

//空间最小，不用使用栈
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()<=2)
            return 0;
        int water=0;
        int max_h=0;
        
        vector<int>::iterator it=height.begin();
        vector<int>::iterator it_max=it;
        max_h=*it;
        it++;
        for(;it!=height.end();it++)
        {
            if(*it>=max_h)
            {
                for(it_max;it_max!=it;it_max++)
                {
                    water+=max_h-*it_max;
                }
                max_h=*it;
                it_max=it;
            }
        }
        
        it=height.end();
        it--;
        if(it_max!=it)
        {
            max_h=*it;
            vector<int>::iterator it_max2=it;
            bool last=false;
            while(true)
            {
                if(*it>=max_h)
                {
                    for(it_max2;it_max2!=it;it_max2--)
                    {
                        water+=max_h-*it_max2;
                    }
                    max_h=*it;
                    it_max2=it;
                }
                it--;
                if(last)
                {
                    break;
                }
                if(it==it_max){
                    last=true;
                }
            }
        }
        

        return water;
    }
};